#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/10/26 16:55
# ===========================================
#       题目名称： 62. 不同路径
#       题目地址： https://leetcode.cn/problems/unique-paths/
#       题目描述： https://note.youdao.com/s/VjIUrvCD
# ===========================================


class Solution:
    """
        3 * 2
        S   1
        1   2
        2   F - 3

        3* 3
        S   1   1       - S -> S+1 [左边为1  上边为0 ] = 1       -> S + 2 [左 1  上0]   1
        1   2   3       - S ->  [左0 上 1] 1     ->  [左  1   上1]  2 ->  [左  2   上1]  3
        1   3   F       - S ->  [左0 上 1] 1     ->  [左  1   上2]  3 ->  [左  3   上3]  6

        使用动态规划
    """

    def uniquePaths(self, m: int, n: int) -> int:
        # 1. 定义动态规划列表
        dp = [[1] * n for _ in range(m)]
        # 2. 进行填充
        for x in range(len(dp)):
            for y in range(len(dp[x])):
                # 检查上面和左边是否有值  就是左边和上边都没有可能性 就取1
                t, l = 0, 0
                if x - 1 > -1 and y - 1 > -1:
                    l = dp[x - 1][y]
                    t = dp[x][y - 1]
                    dp[x][y] = t + l
                else:
                    dp[x][y] = 1
        return dp[m - 1][n - 1]


if __name__ == '__main__':
    s = Solution()
    # 28
    print(" m = 3, n = 7 =>", s.uniquePaths(m=3, n=7))
    # 3
    print(" m = 3, n = 2 =>", s.uniquePaths(m=3, n=2))
    # 28
    print(" m = 7, n = 3 =>", s.uniquePaths(m=7, n=3))
    # 6
    print(" m = 3, n = 3 =>", s.uniquePaths(m=3, n=3))
    # 1
    print(" m = 1, n = 1 =>", s.uniquePaths(m=1, n=1))
